import { checkArr } from "./util"

/**
 * 插入排序
 * @param arr 
 */
export const insertionSort = (arr: number[]) => {
    // 校验数组
    if (checkArr(arr)) return;

    /**
     * 二分查找第一个比它小的元素
     * @param arr 
     */
    const binarySearch = (e: number, ele: number) => {
        const compare = (l: number, r: number) => l - r

        // 起始和结束索引
        let s = 0;
        while (s <= e) {

            // 获取中间位置的元素
            let half = (s + e) >> 1;

            // 中间位置元素和ele比较大小 
            const cmp = compare(arr[half], ele);

            if (cmp > 0) {
                // 中间元素大于所找的元素，往前
                e = half - 1
            } else {
                // 中间元素小于等于所找的元素，往后找
                s = half + 1
            }
        }
        // 到这说明要插入到0的位置
        return s
    }

    // 获取数组长度 
    const len = arr.length;

    /**
     * 比较
     * @param l 
     * @param r 
     */
    const compare = (l: number, r: number) => arr[l] - arr[r]

    /**
     * 移动元素的位置
     * @param s 
     * @param e 
     */
    const move = (s: number, e: number) => {
        for (let i = e; i > s; i--) {
            arr[i] = arr[i - 1];
        }
    }

    // 排序
    for (let i = 1; i < len; i++) { // 控制次数
        // 1. 保存i位置的元素
        const inserted = arr[i]

        // 2. 往前找到比i位置第一个小的元素
        const p = binarySearch(i - 1, inserted)


        // 3. 移动这些元素
        if (p < i) {
            move(p, i)

            // 4. 将待插入元素插入p位置, 只有移动元素，才插入到该位置
            arr[p] = inserted
        }
    }
}


/**
 * 插入排序
 * @param arr 
 */
export const insertionSort2 = (arr: number[]) => {
    // 校验数组
    if (checkArr(arr)) return;

    // 获取数组长度 
    const len = arr.length;

    /**
     * 比较
     * @param l 
     * @param r 
     */
    const compare = (l: number, r: number) => arr[l] - arr[r]

    /**
     * 移动元素的位置
     * @param s 
     * @param e 
     */
    const move = (s: number, e: number) => {
        for (let i = e; i > s; i--) {
            arr[i] = arr[i - 1];
        }
    }

    // 排序
    for (let i = 1; i < len; i++) { // 控制次数
        let p = -1
        for (let j = i - 1; j >= 0; j--) { // 比较
            if (compare(j, i) > 0) {
                // j 比i大， 记录位置
                p = j;
            }
        }

        // i之前有元素比它大
        if (p !== -1) {
            // 1. 保留改元素
            const inserted = arr[i];

            // 2. [p,  i) 的整体元素往i位置移动
            move(p, i);

            // 3. 元素插入p位置
            arr[p] = inserted
        }

    }
}